package com.soecode.lyf.util;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
import java.util.Random;

public class Cuckoo {
    // 表
    private String[] elements;
    // 默认大小
    private static final int DEFAULT_SIZE = 7;
    // 实际大小
    private int size;
    // 重复Hash
    private int reHash = 0;
    // 重试次数
    private int tryCount = 33;

    //
    private BitSet tt = new BitSet();

    List<HashAlgorithm> hashAlgorithmList = new ArrayList<HashAlgorithm>();

    {
        // 初始2个换散列函数。
        hashAlgorithmList.add(new HashAlgorithm(17));
        hashAlgorithmList.add(new HashAlgorithm(23));
    }

    ;

    public Cuckoo() {
        this(DEFAULT_SIZE);
    }


    public Cuckoo(int size) {
        elements = new String[size];
    }

    /**
     * 移除
     *
     * @param key
     */
    public void remove(String key) {
        if (key == null) {
            return;
        }
        // 遍历算法集合 计算index值
        for (HashAlgorithm hashAlgorithm : hashAlgorithmList) {
            int hashCode = hashAlgorithm.hashCode(key);
            int index = getIndex(hashCode);
            if (elements[index] != null && elements[index].equals(key)) {
                elements[index] = null;
                size--;
            }
        }
    }

    /**
     * 插入
     *
     * @param key
     */
    public void insert(String key) {
        while (true) {
            for (int i = 0; i < tryCount; i++) {

                for (HashAlgorithm hashAlgorithm : hashAlgorithmList) {//遍历算法集合 计算index值，
                    int hashCode = hashAlgorithm.hashCode(key);
                    int index = getIndex(hashCode);
                    if (elements[index] == null) {
                        // 当表中索引无值，将元素放到表中
                        elements[index] = key;
                        size++;
                        return;
                    }
                }

                // 执行到这说明 算法集合计算的index全部有值 进行替换操作
                // 随机选取一个函数
                int hashAlgorithmListIndex = new Random().nextInt(hashAlgorithmList.size());
                int hashCode = hashAlgorithmList.get(hashAlgorithmListIndex).hashCode(key);
                int index = getIndex(hashCode);

                // 原本表中这个索引对应的值
                String oldKey = elements[index];
                // 把要插入的值 放到当前索引上
                elements[index] = key;
                // 现在就是要插入原来替换掉的值
                key = oldKey;

            }
            // 说明要进行扩容操作了
            if (++reHash > 1 || size >= elements.length) {
                expandElements();
                reHash = 0;
            } else {
                // 重新计算hash值
                computeHash();
            }
        }
    }

    /**
     * 更新 hash函数 重新计算
     */
    private void computeHash() {
        // 清空原有的函数
        hashAlgorithmList.clear();
        int one = new Random().nextInt(100);
        int two = new Random().nextInt(100);
        // 只是两个不一样的值
        two = (one != two) ? two : two * 2;
        hashAlgorithmList.add(new HashAlgorithm(one));
        hashAlgorithmList.add(new HashAlgorithm(two));
        rehash(elements.length);
    }

    private void expandElements() {
        rehash(nextPrime(elements.length * 2));
    }

    /**
     * 重新计算所有的 hash 同时放到表中
     *
     * @param length
     */
    private void rehash(int length) {
        System.out.println(length);
        String[] oldArray = elements;
        elements = new String[length];
        size = 0;
        for (String string : oldArray) {
            if (string != null) {
                insert(string);
            }
        }
    }


    /**
     * 素数计算
     *
     * @param begin
     * @return
     */
    public Integer nextPrime(Integer begin) {
        int i;
        int j;
        for (i = begin; ; i++) {
            boolean flag = true;
            for (j = 2; j <= i / 2; j++) {
                if (i % j == 0) {
                    flag = false;
                    break;
                } else if (i % j != 0) {
                    continue;
                } else {
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
    }

    /**
     * 是否包含当前元素
     *
     * @param key
     * @return
     */
    public Boolean cotains(String key) {
        for (HashAlgorithm hashAlgorithm : hashAlgorithmList) {
            int hashCode = hashAlgorithm.hashCode(key);
            int index = getIndex(hashCode);
            if (elements[index] != null) {
                return true;
            }
        }
        return false;
    }


    /**
     * 获取hash值对应的表中索引
     *
     * @param hashCode
     * @return
     */
    private int getIndex(int hashCode) {
        int index = hashCode % elements.length;
        index = index < 0 ? index + elements.length : index;
        return index;
    }

    /**
     * 获取大小
     *
     * @return
     */
    public int getSize() {
        return size;
    }

    /**
     * 定义散列函数集合
     */
    class HashAlgorithm {

        private int initNumber;

        public HashAlgorithm(int initNumber) {
            super();
            this.initNumber = initNumber;
        }

        public int hashCode(String key) {
            return (initNumber + key).hashCode();//传递进来的固定值 +key 模拟两个不同的 hashcode
        }
    }

    public static void main(String[] args) {
        Cuckoo cuckoo = new Cuckoo();
        List<String> ints = new ArrayList<String>();
        for (int i = 0; i < 800; i++) {
            String t = "a" + new Random().nextInt(1000);
            ints.add(t);
            cuckoo.insert(t);
        }
//        for (String string : cuckoo.elements) {
//            System.out.println(string);
//        }

        for (String s : ints) {
            System.out.println(cuckoo.cotains(s));
        }
    }
}
